﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace Algorithm.Easy_88_Merge
{
    class MainProject
    {
        static void Main(string[] args)
        {

            int[] nums1 = new int[] {-1,0,0,3,3,3,0,0,0};
            int m = 6;
            int[] nums2 = new int[] { 1,2,2};
            int n = 3;
            Merge(nums1, m, nums2, n);
            foreach (var item in nums1)
            {
                Console.WriteLine(item);
            }
            Console.ReadKey();
        }

        /// <summary>
        /// 填充后排序
        /// </summary>
        /// <param name="nums1"></param>
        /// <param name="m"></param>
        /// <param name="nums2"></param>
        /// <param name="n"></param>
        public static void Merge(int[] nums1, int m, int[] nums2, int n)
        {
            for (int i = 0; i < nums1.Length; i++)
            {
                if (i>=m)
                {
                    nums1[i] = nums2[nums1.Length - i - 1];
                }
            }
            Array.Sort(nums1);
        }

        /// <summary>
        /// 思路：根据m+n定义一个空数组，在每次循环中，填充值，最后在赋值给nums1空间：O（1）
        /// </summary>
        /// <param name="nums1"></param>
        /// <param name="m"></param>
        /// <param name="nums2"></param>
        /// <param name="n"></param>
        public static void Merge1(int[] nums1, int m, int[] nums2, int n)
        {
            int[] sortArray = new int[m + n];
            int mIndex = 0;
            int nIndex = 0;

            for (int i = 0; i < sortArray.Length; i++)
            {
                if (mIndex>=m)
                {
                    sortArray[i] = nums2[nIndex];
                    nIndex++;
                    continue;
                }

                if (nIndex >= n || nums1[mIndex]<= (nums2[nIndex]))
                {
                    sortArray[i] = nums1[mIndex];
                    mIndex++;
                }
                else if(mIndex >= m || nums1[mIndex] > (nums2[nIndex]))
                {
                    sortArray[i] = nums2[nIndex];
                    nIndex++;
                }
            }
            for (int i = 0; i < nums1.Length; i++)
            {
                nums1[i] = sortArray[i];
            }
        }
    }
}
